package 数据结构;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Stack;

/**
 * @author zhangmin
 * @create 2021-12-03 17:46
 */
public class QueueAndStack03 {

    /**==============================================================================================================================================
     * JZ9 用两个栈实现队列
     * 用两个栈来实现一个队列，使用n个元素来完成 n 次在队列尾部插入整数(push)和n次在队列头部删除整数(pop)的功能。 队列中的元素为int类型。保证操作合法，即保证pop操作时队列内已有元素。
     * */
    static class StackToQueue {
        Stack<Integer> stack1 = new Stack<Integer>();
        Stack<Integer> stack2 = new Stack<Integer>();

        public void push(int node) {
            stack1.push(node);
        }

        public int pop() {
            //当stack2为空时、将stack1中的元素依次取出放到stack2，中，然后pop，stacke2
            if (stack2.isEmpty()){
                while (!stack1.isEmpty()){
                    stack2.push(stack1.pop());
                }
            }
            return stack2.pop();
        }
    }

    /**==============================================================================================================================================
     * JZ30 包含min函数的栈
     * 定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的 min 函数，输入操作时保证 pop、top 和 min 函数操作时，栈中一定有元素。
     * */
    public class MinStack {

        int min=Integer.MAX_VALUE;
        Stack<Integer> stack=new Stack<>();

        public void push(int node) {
            //可以保证入栈的元素是由大到小，栈顶是最小的元素
            if (node<=min){
                //将上一个最小的元素压入栈，min记录最小元素
                stack.push(min);
                min=node;
            }
            stack.push(node);
        }

        public void pop() {
            if (stack.pop()==min)
                min=stack.pop();
        }

        public int top() {
            return stack.peek();
        }

        public int min() {
            return this.min;
        }
    }

    /**==============================================================================================================================================
     * JZ31 栈的压入、弹出序列
     * 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。
     * 例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。
     * 思路：利用辅助栈，按照入栈顺序进行入栈，在入栈时判断栈顶元素是否与pop中遍历到的当前元素相等，相等的时候出栈，最后判断栈是否为空
     * */
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        Stack<Integer> stack=new Stack<>();
        int index=0;
        for (int pushNUm:pushA) {
            stack.push(pushNUm);
            while (!stack.isEmpty()&&stack.peek()==popA[index]){
                stack.pop();
                index++;
            }
        }
        return stack.isEmpty();
    }

    /**==============================================================================================================================================
     * JZ73 翻转单词序列
     * 牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，
     * 有一天他向Fish借来翻看，但却读不懂它的意思。例如，“nowcoder. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a nowcoder.”。
     * */
    public String ReverseSentence(String str) {
        if (str.length()<=1) return str;
        String[] strings = str.split(" ");
        StringBuffer sb=new StringBuffer();
        for (int i = strings.length-1; i >=0 ; i--) {
            String s=strings[i];
            if (!s.equals(" ")){
                sb.append(s).append(" ");
            }
        }
        String res=sb.toString();
        return res.substring(0,res.length()-1);
    }

    /**==============================================================================================================================================
     * JZ59 滑动窗口的最大值
     * 给定一个长度为 n 的数组 num 和滑动窗口的大小 size ，找出所有滑动窗口里数值的最大值。
     * 单调队列：在一堆数字中，已知最值为 A，如果给这堆数添加一个数 B，那么比较一下 A 和 B 就可以立即算出新的最值；但如果减少一个数，就不能直接得到最值了，
     * 因为如果减少的这个数恰好是 A，就需要遍历所有数重新找新的最值。
     * */
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        if (num.length==0||size==0) return new ArrayList<>();
        if (size>num.length)return new ArrayList<>();
        ArrayList<Integer> res=new ArrayList<>();

        //单调队列
        MonotonicQueue window=new MonotonicQueue();
        for (int i = 0; i < num.length; i++) {
            if (i<size-1){
                window.push(num[i]);
            }else {
                window.push(num[i]);
                //将当前窗口最大值加入结果
                res.add(window.max());
                window.pop(num[i-size+1]);
            }
        }
        return res;
    }
    class MonotonicQueue{
        // 双链表，支持头部和尾部增删元素
        private LinkedList<Integer> q = new LinkedList<>();

        public void push(int n){
            //将前面比n小的元素都移除
            while (!q.isEmpty()&&q.getLast()<n){
                q.pollLast();
            }
            q.addLast(n);
        }
        public int max(){
            return q.getFirst();
        }
        public void pop(int n){
            //有可能要删除的n，已经在之前push的时候被删除了
            if (n==q.getFirst()){
                q.pollFirst();
            }
        }
    }

}
